I. Field of the Invention
The present invention relates to the compression of graylevel data images.
II. Prior and Contemporaneous Technology
In many applications, an image is to be communicated rapidly or is to be contained in limited storage.
Typically, the image is partitioned into numerous picture elements to facilitate the processing of image data. A picture element is typically referred to as a "pixel" or "pel".
Generally, the image is defined as m lines of n pixels/line. Collectively, the lines of pixels represent the image.
Each pixel may be white or black, or may have a graylevel (or grayscale) value associated therewith. The binary or multilevel data is normally provided in digital form, which facilitates communication and storage thereof.
One way of representing the information contained in an image is to scan the pixels line-by-line and provide the value for each pixel. For example, suppose the upper left pixel is identified as X.sub.1,1 where the first subscript corresponds to the line number and the second subscript corresponds to the pixel in the line. The second pixel in the first line is then X.sub.1,2. If there are 480 lines and 512 pixels/line, an image for a given instant can be represented by information gathered by scanning the 480.times.512 pixels.
In a graylevel image, each pixel has a graylevel value assigned thereto, ranging between a black value (e.g., 0) and a white value (e.g., 255). That is, given 8 bits, the graylevel of a pixel can have any of 256 values. Proceeding line-by-line, an image can be represented by the successively recorded values of pixels X.sub.1,1, X.sub.1,2, . . . , X.sub.480,512.
Typically in the past, a top-to-bottom scan of the image has been referred to as a "field" and a plurality of fields have been interlaced to form a "frame". For example, one field may comprise the odd-numbered lines which are scanned first and a second field may comprise the even-numbered lines which are scanned thereafter. The two fields together form a single "frame".
The above straightforward approach results in a large number of bits required for each image to be recorded. The large number of bits can make the storing and/or rapid conveying of data impractical where storage space is limited or rapid data transfer is required. It is thus desirable to reduce, or compress, the number of bits required to represent the graylevel data.
To address the problem of reducing the number of required bits, a number of data compression techniques have been taught.
One technique of data compression is referred to as "entropy coding". In entropy coding, the number of bits used in representing events is intended to be inversely related to event probability. More probable events are represented by code-words characterized by a relatively short length (of bits) whereas less probable events are represented by relatively longer lengths.
To perform entropy coding, an entropy coder typically receives two inputs. The first input is a decision and the second input is a state input which provides a context for the decision input. For example, a binary decision input may represent a heads or tails event for a coin toss; or an ON or OFF condition for a switch; or a 1 or 0 value of a bit in a string. The state input--usually based on history, theory, or estimate--provides some contextual index for the decision input. For example, in an image in which a pixel may be either black or white, different neighborhoods of the image may have different likelihoods of a pixel therein being white. That is, each neighborhood has a respective estimated black-white probability ratio associated therewith. Hence, to provide meaning to the decision input, a state input is furnished to reflect the neighborhood corresponding to the decision input. Based on the state input, the entropy coder transforms the decision input into a code-word of appropriate length. The state input to the entropy coder is the result of modelling, i.e. defining the contexts in which code-words are assigned to decisions. A well-known example of modelling involves Markov states. The compression of the entropy encoder depends on the quality of the modelling--that is, how well the state input to the entropy coder represents the actual decision context, e.g. The decisional probability given the context neighborhood.
The correct assignment of code-word lengths is dictated by information theory concepts and is based on the estimated probability of occurrence of the possible decision outcomes. The better the probability estimate, the more efficient the code-word length assignment, and the better the compression.
One example of an entropy coder is described in detail in co-pending patent applications:
"ARITHMETIC CODING DATA COMPRESSION/DE-COMPRESSION BY SELECTIVELY EMPLOYED, DIVERSE ARITHMETIC CODING ENCODERS AND DECODERS", invented by J. L. Mitchell and W. B. Pennebaker, U.S. Ser. No. 06/907,700; "PROBABILITY ESTIMATION BASED ON DECISION HISTORY", invented by J. L. Mitchell and W. B. Pennebaker, U.S. Ser. No. 06/907,695; and "ARITHMETIC CODING ENCODER AND DECODER SYSTEM" (Q-coder), invented by G. G. Langdon, Jr., J. L. Mitchell, W. B. Pennebaker and J. J. Rissanen, U.S. Ser. No. 06/907,714.
The invention disclosed in the above-cited co-pending patent applications were invented by the present inventors and co-workers thereof at, and are all assigned to, the IBM Corporation; said applications being incorporated herein by reference for their teachings involving entropy coding, or more specifically arithmetic coding and adaptive probability estimation.
Other entropy coders include Huffmann coding coders and Elias coding coders. Numerous publications describe such coding approaches.
Another technique used in data compression is referred to as "Differential Pulse Code Modulation" (DPCM), which is a form of "predictive coding". According to basic DPCM teachings, a predicted value based on one or more neighboring pixel values is determined for a "subject" pixel--i.e., a pixel whose informational content is currently being coded. The difference between the value for the subject pixel and the predicted value is then used as a basis for subsequent coding. Where there is high correlation between nearby pixels, using the difference value rather than the actual graylevel value can result in significant compression. Typically, a factor-of-two compression can be achieved by using predictive coding techniques to obtain reasonably good quality pictures. A patent application filed by the present inventors and also assigned to IBM Corporation, U.S. Ser. No. 946,542, filed Dec. 22, 1986, relates to an "Adaptive Graylevel Image Compression System" in which the DPCM prediction error is quantized and entropy encoded. The apparatus and method set forth therein may be used in coding values for all pixels in an image. Alternatively, however, the method may be applied to coding just pixels where alternate rows and alternate columns intersect. Such pixels may represent a first pattern which is interlaced with another pattern to form the complete image. A pixel X in the first pattern has a pixel A to the left thereof (in said first pattern); a pixel B to the upper left diagonal (in said first pattern); a pixel C adjacent and above (in said first pattern); and pixel D to the upper right diagonal (in said first pattern). From data derived from pixels A,B,C, and D, data for pixel X is determined. By processing successive pixels in a line, one-line-after-another in the first pattern, all pixels in the first pattern are coded. In U.S. Pat. No. 4,488,174, an approach is proposed in which one field of alternate lines of an image (frame) is encoded from data derived during the prior encoding of pixels in the other field. That is, the algorithm encodes pixels in the "missing" rows.
The encoding of pixels in the missing rows and missing columns--which result from processing pixels in the first pattern discussed hereinabove--is not disclosed by any known prior or contemporaneous technology.